package interview.hw_od;

import java.util.Scanner;

/**
 * 代表团坐车 https://codefun2000.com/p/P1334
 * 题目简述：根据各代表团人数计算有多少种安排可以刚好让车坐满
 */
public class RidePlan {

    /**
     * 思路：01背包-组合问题
     * 1. 定义dp: dp[i][j]为从前i个团中选刚好能装满容量j的方案数
     * 2. 状态转移公式：分为以下两种情况，故dp[i][j] = 情况1 + 情况2
     *          （1）不选第i个团，dp[i][j] = dp[i-1][j]
     *          （2）选第i个团，若容量够且dp[i-1][j-nums[i-1]]不为0，则dp[i][j] = dp[i-1][j-nums[i-1]]
     * 3. 初始化：由于物品重量都大于0，故容量为0则只有空集一种方案 dp[i][0]=1 ； dp[0][j]=0
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] ss = sc.nextLine().split(",");
        int[] nums = new int[ss.length];
        for (int i = 0;i < ss.length;i++)
            nums[i] = Integer.parseInt(ss[i]);
        int cap = Integer.parseInt(sc.nextLine());
        int[][] dp = new int[nums.length+1][cap+1];
        for (int i = 0;i <= nums.length;i++) {
            dp[i][0] = 1;
        }
        for (int i = 1;i <= nums.length;i++) {
            for (int j = 1;j <= cap;j++) {
                if (nums[i-1] > j)
                    dp[i][j] = dp[i-1][j];
                else dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
            }
        }
        System.out.println(dp[nums.length][cap]);
    }
}
